// Package coding_round_1 20-3
// @Title coding_round_1
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/10 16:40
// @Create  2021/9/10 16:40
package coding_round_1

func isSubStr(s string) bool {
	// 判断一个字符串是否包含无重复数据
	if s == "" || len(s) < 1 {
		return true
	}
	uniMap := make(map[byte]int, 0)
	for i := 0; i < len(s); i++ {
		if uniMap[s[i]] >= 1 {
			return false
		} else {
			uniMap[s[i]]++
		}
	}
	return true
}

// LengthOfLongestSubstring 无重复子串的最长长度 AC 但是5%的通过率 有点低 妈的
func LengthOfLongestSubstring(s string) int {
	if s == "" || len(s) < 1 {
		return 0
	}
	ans := 0
	//fmt.Println(s,isSubStr(s))
	// 定义一个map 判断这个字符串有没有重复数字 {"a":1,"b":2}
	l, r := 0, 0 // 初始化两个指针
	for r <= len(s) {
		tempStr := s[l:r]
		// 左小于右 且当前字符串包含了重复数据
		for l <= r && !isSubStr(tempStr) {
			l++
			tempStr = s[l:r]
		}
		if r-l > ans {
			ans = r - l
		}
		//fmt.Println(l,r,ans,tempStr)
		r++
	}
	return ans
}

// 优化后能提升到47%
func lengthOfLongestSubstring(s string) int {
	// 哈希集合，记录每个字符是否出现过
	m := map[byte]int{}
	n := len(s)
	// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
	rk, ans := -1, 0
	for i := 0; i < n; i++ {
		if i != 0 {
			// 左指针向右移动一格，移除一个字符
			delete(m, s[i-1])
		}
		for rk+1 < n && m[s[rk+1]] == 0 {
			// 不断地移动右指针
			m[s[rk+1]]++
			rk++
		}
		// 第 i 到 rk 个字符是一个极长的无重复字符子串
		ans = max(ans, rk-i+1)
	}
	return ans
}
